package binarysearch;

// 更优的解法是滑动窗口, O(n), shit.
public class MinimumSizeSubarraySum209 {
    // 方案1, 前缀和, 两两相减, 复杂度O(n2)
    // 方案2, 前缀和, 固定left, 二分搜索right. 已通过.
    public int minSubArrayLen(int target, int[] nums) {
        // prefixSum[i+1] = sum(nums[0], ..., nums[i])
        int[] prefixSum = new int[nums.length+1];
        prefixSum[0] = nums[0];
        for (int i = 0; i < nums.length; i++) {
            prefixSum[i+1] = prefixSum[i] + nums[i];
        }

        int minLength = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int left = i + 1;
            int right = nums.length;
            while (left <= right) {
                int mid = (left + right) / 2;
                int subSum = prefixSum[mid] - prefixSum[i];
                if (subSum >= target) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            // left最小为i+1. 当left=i+1时, left-i=1表示nums[i]一个元素就已经大于target了.
            // 当left=nums.length时, left-i对应范围是[i, ..., nums.length-1]
            if (left <= nums.length) {
                minLength = Math.min(minLength, left - i);
            }
        }
        return (minLength < Integer.MAX_VALUE) ? minLength : 0;
    }
}
